/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/add-two-numbers
   @Language: C++
   @Datetime: 16-02-09 04:40
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
	/**
	 * @param l1: the first list
	 * @param l2: the second list
	 * @return: the sum list of l1 and l2 
	 * Tip : list head is small bit, list tail is big bit
	 */
	ListNode *addLists(ListNode *l1, ListNode *l2) {
		// write your code here
		if(l1==NULL || l2==NULL) return l1?l1:l2;
		ListNode H(0), *p=&H;
		for(int carry=0; l1 || l2 || carry; carry/=10){
			if (l1) carry += l1->val, l1=l1->next;
			if (l2) carry += l2->val, l2=l2->next;
			p=p->next=new ListNode(carry%10);
		}
		return H.next;
	}
};
